package com.my.study.algorithm.linked;

/**
 * @author Carlos
 * @version 1.0
 * @Description 合并两个排序的链表
 * <p> 输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
 * 数据范围： 0 <= n <= 10000，-1000 <= 节点值 <= 1000
 * 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
 *
 * @date 2021/10/27 7:35
 **/
public class MergeLink {

    public static void main(String[] args) {
        ListNode node3 = new ListNode(5, null);
        ListNode node2 = new ListNode(2, node3);
        ListNode l1 = new ListNode(-1, node2);

        ListNode node5 = new ListNode(4, null);
        ListNode node4 = new ListNode(3, node5);
        ListNode l2 = new ListNode(1, node4);


        ListNode merge = merge(l1, l2);

        System.out.println(merge);
    }


    public static ListNode merge(ListNode list1,ListNode list2) {
        if (null == list1) {
            return list2;
        }
        if (null == list2) {
            return list1;
        }

        // 新建一个头node
        ListNode head = new ListNode(0);
        ListNode moveNode = head;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                moveNode.next = list1;
                list1 = list1.next;
            }
            else {
                moveNode.next = list2;
                list2 = list2.next;
            }
            moveNode = moveNode.next;
        }

        if (list1 != null) {
            moveNode.next = list1;
        }
        if (list2 != null) {
            moveNode.next = list2;
        }

        return head.next;
    }
}
